﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Text;

namespace Exprevolution
{
    class Program
    {
        static void Main(string[] args)
        {
            var creature = new Creature();
        }
    }

    class Creature
    {
        /// <summary>
        /// Constructs a random creature.
        /// </summary>
        public Creature()
        {
                // build a temporary node representing the executable portion of the genome
            var exeNode = this.BuildRandomExpression(0);
            Console.WriteLine("{0} variables defined", this.variableMap.Count);
            Console.WriteLine(exeNode.Expression);

                // build a node containing the variable declarations plus the executable code
            var expr = Expression.Block(
                this.variableMap.Keys,
                exeNode.Expression);
            this.genome = new ExpressionNode(expr, exeNode);

            var result = Expression.Lambda<Func<int>>(expr).Compile().Invoke();
            Console.WriteLine(result);
        }

        /// <summary>
        /// Root of this creature's expression tree.
        /// </summary>
        ExpressionNode genome;

        /// <summary>
        /// Builds a random expression tree and wraps it in a node.
        /// </summary>
        ExpressionNode BuildRandomExpression(int depth)
        {
            ExpressionNode node = null;

            var rand = (depth > 15) ? 0 : rng.Next(3);
            switch (rand)
            {
                case 0:
                    node = BuildRandomLeafExpression(depth);
                    break;

                case 1:
                case 2:
                    node = BuildRandomInternalExpression(depth);
                    break;

                default:
                    throw new Exception();
            }

            return node;
        }

        ExpressionNode BuildRandomLeafExpression(int depth)
        {
            Expression expr = null;

            var rand = (this.variableList.Count == 0) ? 0 : rng.Next(2);
            switch (rand)
            {
                    // constant
                case 0:
                    expr = Expression.Constant(rng.Next(-100, 100));
                    break;

                    // existing variable
                case 1:
                    expr = this.variableList[rng.Next(this.variableList.Count)];
                    break;

                default:
                    throw new Exception();
            }

            return new ExpressionNode(expr);
        }

        ExpressionNode BuildRandomInternalExpression(int depth)
        {
            Expression expr = null;
            ExpressionNode[] childNodes;

            var rand = rng.Next(3);
            switch (rand)
            {
                    // call an n-ary function
                case 0:
                {
                    int arity;
                    var del = Operations.Random(rng, out arity);
                    childNodes = Enumerable.Range(1, arity)
                        .Select(i => BuildRandomExpression(depth + 1))
                        .ToArray();
                    expr = Expression.Call(
                        del.Method,
                        childNodes.Select(node => node.Expression));
                    break;
                }

                    // ternary if-statement (a == 0 ? b : c)
                case 1:
                {
                    childNodes = Enumerable.Range(1, 3)
                        .Select(i => BuildRandomExpression(depth + 1))
                        .ToArray();
                    var test = Expression.Equal(
                        childNodes[0].Expression,
                        Expression.Constant(0));
                    expr = Expression.Condition(
                        test,
                        childNodes[1].Expression,
                        childNodes[2].Expression);
                    break;
                }

                    // create and bind a new variable
                case 2:
                {
                        // create a value to bind to a new variable
                    var childNode = BuildRandomExpression(depth + 1);

                        // create the variable
                    var variable = Expression.Variable(
                        typeof(int),
                        string.Format("var{0}", this.variableMap.Count));

                        // bind the variable to the value
                    expr = Expression.Assign(
                        variable,
                        childNode.Expression);

                        // add the new variable to the list of available variables
                    this.variableList.Add(variable);
                    this.variableMap[variable] = new List<Expression>();

                    childNodes = new ExpressionNode[] { childNode };

                    break;
                }

                default:
                    throw new Exception();
            }

            return new ExpressionNode(expr, childNodes);
        }

        static Random rng = new Random(0);

        IDictionary<ParameterExpression /*variable*/, IList<Expression> /*references*/> variableMap
            = new Dictionary<ParameterExpression, IList<Expression>>();

        IList<ParameterExpression> variableList = new List<ParameterExpression>();
    }

    class ExpressionNode
    {
        public ExpressionNode(Expression expr, params ExpressionNode[] children)
        {
            this.expression = expr;
            this.children = children;
        }

        public Expression Expression
        {
            get { return this.expression; }
        }
        private Expression expression;

        public IList<ExpressionNode> Children
        {
            get { return this.children; }
        }
        private IList<ExpressionNode> children;

        public override string ToString()
        {
            return this.expression.ToString();
        }
    }

    class Operations
    {
        public static Delegate Random(Random rng, out int arity)
        {
            var rand = rng.Next(arity1.Length + arity2.Length);
            arity = (rand < arity1.Length) ? 1 : 2;
            return (arity == 1)
                ? (Delegate) arity1[rand]
                : arity2[rand - arity1.Length];
        }

        static Func<int, int>[] arity1 =
        {
            Neg,
            Not
        };

        static Func<int, int, int>[] arity2 =
        {
            Add,
            Mult,
            Div,
            Mod,
            Gt,
            Eq,
            And,
            Or
        };

        static int Add(int a, int b)
        {
            return a + b;
        }

        static int Neg(int a)
        {
            return -a;
        }

        static int Mult(int a, int b)
        {
            return a * b;
        }

        static int Div(int a, int b)
        {
            return (b == 0) ? 0 : a / b;
        }

        static int Mod(int a, int b)
        {
            return (b == 0) ? 0 : a % b;
        }

        static int Gt(int a, int b)
        {
            return ToInt(a > b);
        }

        static int Eq(int a, int b)
        {
            return ToInt(a == b);
        }

        static int And(int a, int b)
        {
            return ToInt(ToBool(a) && ToBool(b));
        }

        static int Or(int a, int b)
        {
            return ToInt(ToBool(a) || ToBool(b));
        }

        static int Not(int a)
        {
            return ToInt(!ToBool(a));
        }

        static int ToInt(bool b)
        {
            return b ? 1 : 0;
        }

        static bool ToBool(int a)
        {
            return a != 0;
        }
    }
}
